//
// GPSMapEdit
// (c) Konstantin Galichsky (kg@geopainting.com), 2002-2007
//
// Objects of map.
//

# include "StdAfx.h"
# include "Map.h"
# include "Types.h"
# include "Log.h"
# include "Status.h"
# include "Globals.h"

void rgn_element_t::swap (rgn_element_t & _other) {
	points.swap (_other.points);
	rectBound.swap (_other.rectBound);
	std::swap (cLevel,        _other.cLevel);
	std::swap (cFileOffset,   _other.cFileOffset);
	std::swap (fLengthOrArea, _other.fLengthOrArea);
	std::swap (bHole,         _other.bHole);
	std::swap (bDeleted,      _other.bDeleted);
	pExtra.swap (_other.pExtra);
}

void rgn_origin_t::swap (rgn_origin_t & _other) {
	std::swap (point,         _other.point);
	std::swap (cLevel,        _other.cLevel);
	std::swap (cFileOffset,   _other.cFileOffset);
	std::swap (bDeleted,      _other.bDeleted);
}

bool rgn_element_t::IsHoleOf (const rgn_element_t & _Outer) const {
	if (
		_Outer.cLevel != cLevel ||
		_Outer.fLengthOrArea < 1.e-10f || _Outer.fLengthOrArea < fLengthOrArea ||
		! _Outer.rectBound.Contains (rectBound)
	)
		return false;

	assert (! _Outer.points.empty ());
	assert (! points.empty ());
	for (size_t cInnerPoint = 0; cInnerPoint < points.size (); ++ cInnerPoint) {
		const int iContains = PolygonContainsPt (_Outer.points, points [cInnerPoint]);
		if (iContains < 0)
			return false;
		else if (iContains > 0)
			return true;
	};

	return false;
}

void rgn_element_t::RemoveRepeatingPoints () {
	if (pExtra == NULL || pExtra->PointExtras.empty ()) {
		::RemoveRepeatingPoints (points);
		return;
	}

	if (! AreThereRepeatingPoints (points))
		return;

	ReleaseRGNodes ();

	epoints_t epoints; 
	Points2EPoints (points, & pExtra->PointExtras, epoints);
	::RemoveRepeatingPoints (epoints);
	EPoints2Points (epoints, true, points, pExtra->PointExtras);

	AddRefRGNodes ();
}

bool rgn_t::Contains (const point_t & _point, float _fE) const {
	const float fCosY = ::cos (_point.y*c_PI/180.f);

	if (! elements.empty ()) {
		const bool bPolygon = IsPolygon ();
		for (rgn_elements_t::const_iterator i = elements.begin (); i != elements.end (); ++ i) {
			const rgn_element_t & elm = *i;
			if (elm.bDeleted)
				continue;

			if (! elm.rectBound.Contains (_point))
				continue;

			if (bPolygon) {
				if (PolygonContainsPt (elm.points, _point) >= 0)
					return true;
			} else {
				if (PolylineContainsPt (elm.points, _point, _fE, fCosY))
					return true;
			}
		}
	} else if (! origins.empty ()) {
		for (rgn_origins_t::const_iterator i = origins.begin (); i != origins.end (); ++ i) {
			const rgn_origin_t & org = *i;
			if (org.bDeleted)
				continue;
			if (PointContainsPt (org.point, _point, _fE, fCosY))
				return true;
		}
	}

	return false;
}

bool rgn_t::IntersectsSegment (const point_t & _ptStart, const point_t & _ptEnd) const {
	if (! elements.empty ()) {
		const float fCosY = ::cos (_ptStart.y*c_PI/180.f);
		const bool bPolygon = IsPolygon ();

		for (rgn_elements_t::const_iterator i = elements.begin (); i != elements.end (); ++ i) {
			const rgn_element_t & elm = * i;
			if (elm.bDeleted)
				continue;

			if (SegmentIntersectsPolyline (_ptStart, _ptEnd, elm.points, bPolygon))
				return true;
		}
	} 

	return false;
}

rgn_element_t * rgn_t::GetNonDeletedElement (size_t _c, size_t _cLevel) {
	const size_t cElements = elements.size ();
	for (size_t cElement = 0; cElement < cElements; ++ cElement) {
		rgn_element_t & element = elements [cElement];
		if (element.bDeleted)
			continue;
		if (_cLevel != -1 && element.cLevel != _cLevel)
			continue;

		if (_c == 0)
			return & element;
		else
			-- _c;
	}

	return NULL;
}

const rgn_element_t * rgn_t::GetNonDeletedElement (size_t _c, size_t _cLevel) const {
	return const_cast<rgn_t *> (this)->GetNonDeletedElement (_c, _cLevel);
}

size_t rgn_t::GetElements () const {
	size_t cRet = 0;
	const size_t cElements = elements.size ();
	for (size_t c = 0; c < cElements; ++ c) {
		const rgn_element_t & element = elements [c];
		if (! element.bDeleted)
			++ cRet;
	}
	return cRet;
}

size_t rgn_t::GetOrigins () const {
	size_t cRet = 0;
	const size_t cOrigins = origins.size ();
	for (size_t c = 0; c < cOrigins; ++ c) {
		const rgn_origin_t & origin = origins [c];
		if (! origin.bDeleted)
			++ cRet;
	}
	return cRet;
}

size_t rgn_t::GetElementsInLevel (size_t _cLevel) const {
	size_t cRet = 0;
	const size_t cElements = elements.size ();
	for (size_t c = 0; c < cElements; ++ c) {
		const rgn_element_t & element = elements [c];
		if (element.bDeleted)
			continue;

		if (
			element.cLevel != _cLevel &&
			! (this->uchEndLevel != 0 && element.cLevel <= _cLevel && _cLevel <= this->uchEndLevel)
		)
			continue;

		++ cRet;
	}
	return cRet;
}

size_t rgn_t::GetOriginsInLevel (size_t _cLevel) const {
	size_t cRet = 0;
	const size_t cOrigins = origins.size ();
	for (size_t c = 0; c < cOrigins; ++ c) {
		const rgn_origin_t & origin = origins [c];
		if (origin.bDeleted)
			continue;

		if (
			origin.cLevel != _cLevel &&
			! (this->uchEndLevel != 0 && origin.cLevel <= _cLevel && _cLevel <= this->uchEndLevel)
		)
			continue;

		++ cRet;
	}
	return cRet;
}

void rgn_t::RefreshAttributes (map_t & _map, bool _bRefereshDrawOrder) {
	rectBound = rect_t ();

	const bool bIsPolygon = IsPolygon ();

	//
	// Explore elements.
	//
	const size_t cElements = elements.size ();
	if (cElements) {
		// Data used to count holes and average element area.
		float fArea = 0;
		size_t cNonHoleParts = 1;

		for (size_t cElement = 0; cElement < cElements; ++ cElement) {
			rgn_element_t & element = elements [cElement];
			if (element.bDeleted)
				continue;

			const points_t & points = element.points;
			const size_t cPoints = points.size ();

			if (cPoints > _map.cMaxPointsInElement)
				_map.cMaxPointsInElement = cPoints;

			// Determine the bounding rectangle.
			element.rectBound = rect_t ();
			for (size_t cPoint = 0; cPoint < cPoints; ++ cPoint) {
				const point_t & point = points [cPoint];

				element.rectBound.Extend (point);
			}
			rectBound.Extend (element.rectBound);

			if (IsPolyline ()) {
				// NOTE: For polylines only.
				element.fLengthOrArea = GetLength (points);
				element.bHole = false;
			} else if (bIsPolygon) {
				// NOTE: count element's area before hole detection.
				element.fLengthOrArea = GetArea (points);

				// NOTE: bHole is not updated here. Please use RefreshHoles() for this.
				if (element.bHole)
					fArea -= element.fLengthOrArea;
				else
					fArea += element.fLengthOrArea;
			}
		}

		fAveElementArea = bIsPolygon ? fArea/cNonHoleParts : 0;
	}
	if (bIsPolygon && _bRefereshDrawOrder) {
		//
		// Re-order polygons draw order.
		//

		// Search for iterator to this polygon.
		rgns_t & polygons = _map.layers [rkPolygon].rgns;
		rgns_t::iterator iThis;
		for (iThis = polygons.begin (); iThis != polygons.end (); ++ iThis) {
			if (& * iThis == this)
				break;
		}
		if (iThis != polygons.end ()) {
			bool bGreaterThenPrev = false;
			if (iThis != polygons.begin ()) {
				rgns_t::iterator iPrev = iThis;
				-- iPrev;
				bGreaterThenPrev = fAveElementArea > iPrev->fAveElementArea;
			}

			bool bLessThenNext = false;
			rgns_t::iterator iNext = iThis;
			++ iNext;
			if (iNext != polygons.end ())
				 bLessThenNext = fAveElementArea < iNext->fAveElementArea;

			if (bGreaterThenPrev || bLessThenNext) {
				// NOTE: the element should be shifted inside the list to restore sort order.

				// Search for the new position in the list.
				rgns_t::iterator iToBeNext;
				for (iToBeNext = polygons.begin (); iToBeNext != polygons.end (); ++ iToBeNext) {
					if (iToBeNext->fAveElementArea < fAveElementArea)
						break;
				}

				// Shift this polygon to the new position.
				polygons.splice (iToBeNext, polygons, iThis);
			}
		} else
			// NOTE: the polyline appears not in the list!
			assert (false);
	}

	//
	// Explore origins.
	//
	for (size_t cOrigin = 0; cOrigin < origins.size (); ++ cOrigin) {
		const rgn_origin_t & origin = origins [cOrigin];
		if (origin.bDeleted)
			continue;

		// Include origins in the bounding rect.
		rectBound.Extend (origin.point);
	}

	_map.rectBound.Extend (rectBound);

	fSize2 = 0;

	//
	// Prepare point for the label, if any.
	//
	if (! strLabel.empty ()) {
		if (cElements)
			fSize2 = GetRgnSize (* this);

		const type_desc_t * const pTD = GetTypeDesc ();
		assert (pTD);
		if (pTD)
			pTD->pfPrepareLabel (* this);
	}
}

void rgn_t::ReorderHoles () {
	const size_t cElements = elements.size ();

	// Array of indices of outer polygons.
	size_t cOuters = 0;
	size_t * const pcOuters = reinterpret_cast<size_t *> (alloca (cElements*sizeof (size_t)));

	// Array of indices of inner polygons.
	size_t cInners = 0;
	size_t * const pcInners = reinterpret_cast<size_t *> (alloca (cElements*sizeof (size_t)));

	for (size_t cElement = 0; cElement < cElements; ++ cElement) {
		const rgn_element_t & element = elements [cElement];
		if (element.bDeleted)
			continue;

		if (element.bHole)
			pcInners [cInners ++] = cElement;
		else
			pcOuters [cOuters ++] = cElement;
	}
	assert (cOuters <= cElements);
	assert (cInners <= cElements);
	assert (cOuters + cInners <= cElements);

	if (cInners == 0 || cOuters == 0)
		// Nothing to do!
		return;

	// Reorder in temporary vector.
	rgn_elements_t elements2 (cOuters + cInners);
	size_t cIndex = 0;

	for (size_t cOuterElement = 0; cOuterElement < cOuters; ++ cOuterElement) {
		assert (pcOuters [cOuterElement] < cElements);
		assert (cIndex < cOuters + cInners);
		elements2 [cIndex].swap (elements [pcOuters [cOuterElement]]);
		const rgn_element_t & elemOuter = elements2 [cIndex ++];

		for (size_t cInnerElement = 0; cInnerElement < cInners; ++ cInnerElement) {
			if (pcInners [cInnerElement] == -1)
				// Already visited.
				continue;

			assert (pcInners [cInnerElement] < cElements);
			if (elements [pcInners [cInnerElement]].IsHoleOf (elemOuter)) {
				assert (cIndex < cOuters + cInners);
				elements2 [cIndex ++].swap (elements [pcInners [cInnerElement]]);

				// Mark to avoid second visiting.
				pcInners [cInnerElement] = -1;
			}
		}
	}
	// NOTE: some inners may appear outside of any of outers.
	if (cIndex < cOuters + cInners) {
		// Copy them to the end of the list.
		for (size_t cInnerElement = 0; cInnerElement < cInners; ++ cInnerElement)
			if (pcInners [cInnerElement] != -1) {
				assert (cIndex < cOuters + cInners);
				assert (pcInners [cInnerElement] < cElements);
				elements2 [cIndex ++].swap (elements [pcInners [cInnerElement]]);
			}
	}
	assert (cIndex == cOuters + cInners);

	elements.swap (elements2);
}

void rgn_t::SetType (const CTypeSet * _pTypeSet, USHORT _ushType, BYTE _ushKind) {
	SetType (_pTypeSet->GetTypeDesc (_ushType, _ushKind), _ushType, _ushKind);
}

const type_desc_t * rgn_t::GetTypeDesc () const {
	if (IsTrack () || IsRoute ())
		return g_map.pTypeSet->GetUnknownTD ();

	if (pTypeDesc)
		return pTypeDesc;

	if (IsWaypoint ())
		return g_map.pTypeSet->GetUnknownTD ();
	else {
		assert (false);
		return NULL;
	}
}

bool rgn_t::IsDeleted () const {
	return (dwFlags & fDeleted) || (pFileRef && pFileRef->bDeleted);
}

void rgn_t::Delete (map_t & _map, bool _bReleaseRGNodes) {
	if ((dwFlags & rgn_t::fDeleted) != 0)
		return;

	dwFlags |= rgn_t::fDeleted;
	++ _map.layers [Kind].cDeletedRgns;

	if (_bReleaseRGNodes)
		ReleaseRGNodes ();
}

void rgn_t::Undelete (map_t & _map, bool _bAddRefRGNodes) {
	if ((dwFlags & rgn_t::fDeleted) == 0)
		return;

	dwFlags &= ~rgn_t::fDeleted;
	-- _map.layers [Kind].cDeletedRgns;

	if (_bAddRefRGNodes)
		AddRefRGNodes ();
}

bool rgn_t::IsPolygon () const {
	const type_desc_t * const pTD = GetTypeDesc ();
	assert (pTD);
	if (! pTD)
		return false;

	return pTD->bUnknown ? (Kind == rkPolygon) : (pTD->Kind == rkPolygon);
}

bool rgn_t::IsPolyline () const {
	const type_desc_t * const pTD = GetTypeDesc ();
	assert (pTD);
	if (! pTD)
		return false;

	return pTD->bUnknown ? (Kind == rkPolyline) : (pTD->Kind == rkPolyline);
}

bool rgn_t::IsPoint () const {
	const type_desc_t * const pTD = GetTypeDesc ();
	assert (pTD);
	if (! pTD)
		return false;

	return pTD->bUnknown ? (Kind == rkPoint) : (pTD->Kind == rkPoint);
}

bool rgn_t::IsRoad () const {
	return IsPolyline () && g_map.pTypeSet->pfIsRoad (* this);
}

bool rgn_t::IsAttachment () const {
	return IsWTR () || (pFileRef && pFileRef->bAttachment);
}

bool rgn_t::IsVisible () const {
	return ! IsDeleted () && (! pFileRef || (pFileRef->bVisible && ! pFileRef->bDeleted));
}

void rgn_t::AddCommentLine (const char * _strLine) {
	const size_t cLen = strComment.length ();
	
	bool bNeedCRLF = false;
	if (cLen == 1)
		bNeedCRLF = true;
	else if (cLen > 1)
		bNeedCRLF = (strComment [cLen - 2] != '\r') || (strComment [cLen - 1] == '\n');

	if (bNeedCRLF)
		strComment.append ("\r\n");

	strComment.append (_strLine);
}

void rgn_element_t::ReleaseRGNodes () {
	if (pExtra == NULL)
		return;

	const size_t cPoints = points.size ();

	point_extras_t & PointExtras = pExtra->PointExtras;
	const size_t cPointExtras = PointExtras.size ();
	for (size_t cPoint = 0; cPoint < cPointExtras; ++ cPoint) {
		rgnode_t * const pRGNode = PointExtras [cPoint].GetRGNode ();
		if (pRGNode) {
			-- pRGNode->btPolylines;

			if (cPoint == 0 || cPoint + 1 == cPoints)
				-- pRGNode->btCardinality;
			else
				pRGNode->btCardinality -= 2;
		}
	}
}

void rgn_element_t::AddRefRGNodes () {
	if (pExtra == NULL)
		return;

	const size_t cPoints = points.size ();

	point_extras_t & PointExtras = pExtra->PointExtras;
	const size_t cPointExtras = PointExtras.size ();
	for (size_t cPoint = 0; cPoint < cPointExtras; ++ cPoint) {
		rgnode_t * const pRGNode = PointExtras [cPoint].GetRGNode ();
		if (pRGNode) {
			++ pRGNode->btPolylines;

			if (cPoint == 0 || cPoint + 1 == cPoints)
				++ pRGNode->btCardinality;
			else
				pRGNode->btCardinality += 2;
		}
	}
}

void rgn_t::ReleaseRGNodes () {
	if (! IsPolyline () || IsWTR ())
		return;

	const size_t cElements = elements.size ();
	for (size_t cElement = 0; cElement < cElements; ++ cElement) {
		rgn_element_t & element = elements [cElement];
		if (element.bDeleted)
			continue;

		element.ReleaseRGNodes ();
	}
}

void rgn_t::AddRefRGNodes () {
	if (! IsPolyline () || IsWTR ())
		return;

	const size_t cElements = elements.size ();
	for (size_t cElement = 0; cElement < cElements; ++ cElement) {
		rgn_element_t & element = elements [cElement];
		if (element.bDeleted)
			continue;

		element.AddRefRGNodes ();
	}
}

bool rgn_t::HasRGNodes () const {
	if (! IsPolyline () || IsWTR ())
		return false;

	const size_t cElements = elements.size ();
	for (size_t cElement = 0; cElement < cElements; ++ cElement) {
		const rgn_element_t & element = elements [cElement];
		if (element.bDeleted || element.pExtra == NULL)
			continue;

		if (::HasRGNodes (element.pExtra->PointExtras))
			return true;
	}

	return false;
}

float GetRgnSize (const rgn_t & _rgn) {
	const size_t cElements = _rgn.elements.size ();
	if (! cElements)
		return 0;

	float fCosY;
	point_t p0, p1;
	bool b0Defined = false, b1Defined = false;

	float d2max = 0;

	// Find the most distant point for the first one.
	size_t cElement;
	for (cElement = 0; cElement < cElements; ++ cElement) {
		const rgn_element_t & element = _rgn.elements [cElement];
		if (element.bDeleted)
			continue;

		const points_t & points = element.points;
		const size_t cPoints = points.size ();
		if (! cPoints)
			continue;

		for (size_t cPoint = 0; cPoint < cPoints; ++ cPoint) {
			const point_t & point = points [cPoint];

			if (! b0Defined) {
				p0 = point;
				b0Defined = true;
				fCosY = ::cos (point.y*c_PI/180.f);
				continue;
			}

			const float d2 = (p0.x - point.x)*(p0.x - point.x)*fCosY*fCosY + (p0.y - point.y)*(p0.y - point.y);
			if (d2 > d2max) {
				d2max = d2;
				p1 = point;
				b1Defined = true;
			}
		}
	}

	if (! b1Defined)
		return 0;

	// Find the most distant point for the first most distant one.
	for (cElement = 0; cElement < cElements; ++ cElement) {
		const rgn_element_t & element = _rgn.elements [cElement];
		if (element.bDeleted)
			continue;

		const points_t & points = element.points;
		const size_t cPoints = points.size ();
		if (! cPoints)
			continue;

		for (size_t cPoint = 0; cPoint < cPoints; ++ cPoint) {
			const point_t & point = points [cPoint];

			const float d2 = (p1.x - point.x)*(p1.x - point.x)*fCosY*fCosY + (p1.y - point.y)*(p1.y - point.y);
			if (d2 > d2max)
				d2max = d2;
		}
	}

	return d2max;
}

///////////////////////////////////////////////

bool rgn_t::GetDirection (DWORD _dwStartNodeID, DWORD _dwEndNodeID, bool & _bForward) const {
	if (! HasRGNodes ())
		return false;

	const size_t cElements = elements.size ();
	for (size_t cElement = 0; cElement < cElements; ++ cElement) {
		const rgn_element_t & element = elements [cElement];
		if (element.bDeleted)
			continue;

		const point_extras_t & PointExtras = element.pExtra->PointExtras;
		if (PointExtras.empty ())
			continue;

		size_t cStartNode = -1;
		size_t cEndNode   = -1;
		const size_t cPoints = PointExtras.size ();
		for (size_t cPoint = 0; cPoint < cPoints; ++ cPoint) {
			const point_extra_t & point = PointExtras [cPoint];
			const rgnode_t * const pNode = point.GetRGNode ();
			if (pNode == NULL)
				continue;

			if (pNode->dwNodeID == _dwStartNodeID)
				cStartNode = cPoint;
			if (pNode->dwNodeID == _dwEndNodeID)
				cEndNode = cPoint;
		}

		if (cStartNode != -1 && cEndNode != -1) {
			_bForward = cStartNode < cEndNode;
			return true;
		}
	}

	return false;
}

rgnode_t * rgn_element_t::GetNextNode (const rgnode_t * _pNode, bool _bForward) const {
	if (pExtra == NULL)
		return NULL;

	const size_t cPoints = pExtra->PointExtras.size ();
	rgnode_t * pPrevNode = NULL;
	for (size_t cPoint = 0; cPoint < cPoints; ++ cPoint) {
		const point_extra_t & point = pExtra->PointExtras [cPoint];
		rgnode_t * const pNode = const_cast<rgnode_t *> (point.GetRGNode ());
		if (pNode == NULL)
			continue;

		if (_bForward) {
			if (pPrevNode != NULL)
				return pNode;
			if (pNode == _pNode)
				pPrevNode = pNode;
		} else {
			if (pNode == _pNode) {
//				assert (pPrevNode != NULL);
				return pPrevNode;
			}
			pPrevNode = pNode;
		}
	}
	return NULL;
}

rgnode_t * rgn_t::GetNextNode (const rgnode_t * _pNode, bool _bForward) const {
	if (! HasRGNodes ())
		return NULL;

	const size_t cElements = elements.size ();
	for (size_t cElement = 0; cElement < cElements; ++ cElement) {
		const rgn_element_t & element = elements [cElement];
		if (element.bDeleted)
			continue;

		rgnode_t * const pNextNode = element.GetNextNode (_pNode, _bForward);
		if (pNextNode != NULL)
			return pNextNode;
	}
	return NULL;
}

size_t rgn_element_t::FindNode (const rgnode_t * _pNode) const {
	if (pExtra == NULL)
		return -1;

	const size_t cPoints = pExtra->PointExtras.size ();
	for (size_t cPoint = 0; cPoint < cPoints; ++ cPoint) {
		const point_extra_t & point = pExtra->PointExtras [cPoint];
		const rgnode_t * const pNode = point.GetRGNode ();
		if (pNode == NULL)
			continue;

		if (pNode == _pNode)
			return cPoint;
	}
	return -1;
}

bool rgn_element_t::HasNode (const rgnode_t * _pNode) const {
	return FindNode (_pNode) != -1;
}

bool rgn_t::HasNode (const rgnode_t * _pNode) const {
	if (! HasRGNodes ())
		return false;

	const size_t cElements = elements.size ();
	for (size_t cElement = 0; cElement < cElements; ++ cElement) {
		const rgn_element_t & element = elements [cElement];
		if (element.bDeleted)
			continue;

		if (element.HasNode (_pNode))
			return true;
	}
	return false;
}
